Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel

We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP‐hard for any fixed number (≥2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two‐phase heuristics and dynamic two‐phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Maximizing project cash availability

Consider a project during the life cycle of which there are cash payouts and in‐flows. To better meet his financial commitments, the project owner would like to meet all deadlines without running out of cash. We show that the cash availability objective is similar to the total weighted flowtime used to measure work‐in‐progress performance in the scheduling and inventory control literatures. In this article we provide several specialized solution methods for the problem of minimizing total weighted flowtime in an arbitrary acyclic project network, subject to activity release times and due dates, where the activity weights may be positive or negative and represent cash in‐ and out‐flows. We describe the structure of an optimal solution and provide several efficient algorithms and their complexity based on mincost and maxflow formulations. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Optimization and mediated bartering models for ground delay programs

The Federal Aviation Administration (FAA) and the airline community within the United States have adopted a new paradigm for air traffic flow management, called Collaborative Decision Making (CDM). A principal goal of CDM is shared decision‐making responsibility between the FAA and airlines, so as to increase airline control over decisions that involve economic tradeoffs. So far, CDM has primarily led to enhancements in the implementation of Ground Delay Programs, by changing procedures for allocating slots to airlines and exchanging slots between airlines. In this paper, we discuss how these procedures may be formalized through appropriately defined optimization models. In addition, we describe how inter‐airline slot exchanges may be viewed as a bartering process, in which each “round” of bartering requires the solution of an optimization problem. We compare the resulting optimization problem with the current procedure for exchanging slots and discuss possibilities for increased decision‐making capabilities by the airlines. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

架构和模式在水声信息流仿真软件中的应用

水声信息流仿真软件系统涉及多目标、多声纳以及多变的海洋环境.仿真软件的复用性是现代软件工程的重要性能指标.针对系统开放性的特点,在领域分析模型的基础上,采用了面向对象方法设计仿真软件模型.为了满足软件多层次复用的需求,应用软件架构技术和设计模式设计仿真软件.根据水声信息流仿真软件需求,系统划分为四层结构;按功能,层又可分解为包.可复用的设计模式用于设计不同层和包中类之间的关系.提出的仿真软件模型具有良好的可扩充性与可复用性.     

基于蚁群算法的试验流程优化研究

水中兵器的海上试验涉及许多人员、兵力、被试产品、测量设备等,试验周期长、消耗大,因此如何缩短试验周期是亟待研究解决的问题.文中首先将试验流程优化问题转化为车间调度问题,建立了相应的数学模型,再应用蚁群算法转移规则得到中间结果并进行排队以对各种资源约束进行处理.最后将结果利用局部搜索算法优化后作为蚁群算法信息素更新的基础.实例计算结果表明,该方法优化效果良好.     

基于逆向强化学习的舰载机甲板调度优化方案生成方法

针对计算机辅助指挥调度舰载机甲板作业的决策过程无法脱离人参与这一特点,引入基于逆向学习的强化学习方法,将指挥员或专家的演示作为学习对象,通过分析舰载机的甲板活动,建立舰载机甲板调度的马尔可夫决策模型(MDP)框架;经线性近似,采用逆向学习方法计算得到回报函数,从而能够通过强化学习方法得到智能优化策略,生成舰载机甲板调度方案。经仿真实验验证,本文所提方法能够较好地学习专家演示,结果符合调度方案优化需求,为形成辅助决策提供了基础。     

业务流程建模中流程校验的研究与实现

随着计算机网络技术的迅速发展,企业的信息化程度不断提高,以自动化流程为核心理念的工作流管理系统应用越来越普及,对工作流管理系统的可靠性和正确性要求也越来越高.提出了一种工作流建模时的验证方法:在工作流管理系统的工作流建模环境中加入流程验证模块,对建模过程中可能产生的错误进行验证,进而建立简洁实用的流程;通过分析流程中的异常和失败的类型,增强系统的纠错能力,减少引擎处理的压力;对有着特殊应用的建模过程,能够方便地添加自定义的验证条件,为流程的正确运行提供有效的保障;向基于规则化的工作流系统提供建模完整性的方案,获得系统工作流的稳健性.     

基于信息流的中枢疲劳脑电分析

为充分利用多导脑电信息,首次提出运用有向传递函数（DTF）方法,对不同中枢疲劳状态下导联间信息流的强度和方向的变化进行分析。研究结果表明,脑电功能耦合中额一到一顶方向的信息流是大脑皮层联系的一个固有特征,可以有效地刻画安静清醒和疲劳两个状态,长时间脑力劳动任务引起中枢疲劳的增加,进而导致整个频率段占优势的信息流的方向发生了反转,信息流占优势的方向从实验前的顶一到一额方向,转变为实验后的额一到一顶方向。     

卫星任务调度问题的约束规划模型

卫星任务规划与调度是空间资源管理的重要内容之一,其目的在于为卫星系统的任务计划编制提供科学合理的决策手段与依据。卫星任务调度问题的重要特点在于,调度任务存在可见时间窗口约束。只有在可见时间窗口内,调度任务才可能执行并完成。在进行合理假设的基础上,建立卫星任务调度问题的约束规划模型。对基本禁忌搜索算法进行改进,提出了模型求解的变邻域禁忌搜索算法。应用结果表明,约束规划模型的建立与求解是合理的。     

气—固两相自由射流的粒子仿真方法

采用粒子仿真方法直接跟踪颗粒相运动轨迹,采用NND格式求解NS方程,数值模拟了气-固两相自由射流流场.计算结果表明,将粒子仿真与CFD方法相结合是研究气-固两相流动问题的有效途径.颗粒相参数变化将对气体流场产生一定影响.